package com.wu.leetcode.sort.mergesort;

import java.util.Arrays;

/**
 * @author lynn
 * @date 2020/7/12 - 9:51
 * 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，
 * 该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，
 * 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)
 */
    public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2, 67, 45, 8, 34};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            //向左分解
            mergeSort(arr, left, mid);
            //向右分解
            mergeSort(arr, mid + 1, right);

            //合并
            merge(arr, left, right, mid);
        }
    }

    /**
     * 合并
     *
     * @param arr   待排序的数组
     * @param left  左边已排序的子数组
     * @param right 右边已排序的子数组
     * @param mid   划分两个数组的索引
     */
    public static void merge(int[] arr, int left, int right, int mid) {
        //左边数组的起始位置
        int l = left;
        //右边数组的起始位置
        int r = mid + 1;
        //初始化临时数组的长度
        int[] temp = new int[right - left + 1];
        //临时数组的起始位置
        int t = 0;

        //1.将左右两边的数据按照规则填入temp数组
        while (l <= mid && r <= right) {
            //判断并比较，数据依次填入
            temp[t++] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
        }
        //检测哪边未完全填入 将其依次填入
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        while (r <= right) {
            temp[t++] = arr[r++];
        }
        //将temp数组复制到arr
        //注意 不是每次拷贝都是所有的数据
        // 把最终的排序的结果复制给原数组
        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
    }
}
